package basic.study.leetcode;

import java.util.Arrays;

/**
 * @ClassName Mid322
 * @Description 零钱兑换
 * @Company inspur
 * @Author Kevin
 * @Date 2020/7/21 13:04
 * @Version 1.0
 */
public class Mid322 {
    /**
     * 搜索回溯
     */
    class Solution {
        public int coinChange(int[] coins, int amount) {
            return coinChange(0, coins, amount);
        }

        private int coinChange(int idxCount, int[] coins, int amount) {
            if (amount == 0) return 0;
            if (idxCount < coins.length && amount > 0) {
                int maxVal = amount / coins[idxCount];
                int minCost = Integer.MAX_VALUE;
                for (int x = 0; x <= maxVal; x++) {
                    int res = coinChange(idxCount+1, coins, amount-x*coins[idxCount]);
                    if (res != -1) {
                        minCost = Math.min(minCost, res+x);
                    }
                }
                return (minCost == Integer.MIN_VALUE)?-1: minCost;
            }
            return -1;
        }
    }

    /**
     * dp，自上而下
     */
    class Solution1 {
        public int coinChange(int[] coins, int amount) {
            return coinChange(coins, amount, new int[amount]);
        }

        private int coinChange(int[] coins, int amount, int[] count) {
            if (amount < 0) return -1;
            if (amount == 0) return 0;
            if (count[amount-1] != 0) return count[amount-1];

            int minCount = Integer.MAX_VALUE;
            for (int coin: coins) {
                int res = coinChange(coins, amount-coin, count);
                if (res != -1) {
                    minCount = Math.min(minCount, res+1);
                }
            }
            count[amount-1] = (minCount == Integer.MAX_VALUE)?-1:minCount;
            return count[amount-1];
        }
    }

    /**
     * dp,自下而上
     */
    class Solution2 {
        public int coinChange(int[] coins, int amount) {
            int max = amount + 1;
            int[] dp = new int[amount+1];
            Arrays.fill(dp, max);
            dp[0] = 0;
            for (int i = 1; i <= amount; i++) {
                for (int j = 0; j < coins.length; j++) {
                    if (coins[j] <= i) {
                        dp[i] = Math.min(dp[i], dp[i - coins[j]]+1);
                    }
                }
            }
            return dp[amount] > amount?-1: dp[amount];
        }
    }
    /**
     * 贪心
     */
    class Solution3 {
        int ans = Integer.MAX_VALUE;

        public int coinChange(int[] coins, int amount) {
            Arrays.sort(coins);
            coinChange(coins.length-1, coins, 0, amount);
            return ans == Integer.MAX_VALUE?-1:ans;
        }

        private void coinChange(int index, int[] coins, int count, int needAmount) {
            if (needAmount == 0) {
                ans = Math.min(count, ans);
                return;
            }
            if (index<0) {
                return;
            }

            int i = needAmount / coins[index];
            for (int k = i; k >= 0 && count+k<ans; k--) {
                coinChange(index-1, coins, count+k, needAmount - k * coins[index]);
            }
        }
    }
}
